import java.util.ArrayList;

public class Main {
	
	public static void main(String[] args) {
		System.out.println("Example ((big woman man big house),cl)");
		String example = "((big woman man big house),cl)";
		String[] tokens = example.split(",");
		String sentence = tokens[0];
		String expectedValue = tokens[1];
		sentence = sentence.substring(2, sentence.length()-1);
		expectedValue = expectedValue.substring(0,expectedValue.length()-1);
		System.out.println("Sentence: "+sentence);
		System.out.println("Expected Value: "+expectedValue);
		
		System.out.println(bottomUp(sentence,expectedValue));
	}
	
	public static String bottomUp(String sentence, String expectedValue){
		int round = 0 ;
		boolean success = false;
		ArrayList<String> answers = new ArrayList<String>();
		ArrayList<String> newAnswers = new ArrayList<String>();
		ArrayList<String> alreadyConsideredStrings = new ArrayList<String>();
		answers.add(sentence);
		
		while(!answers.isEmpty() && !answers.contains(expectedValue)){
			round = round + 1 ;
			System.out.println("\nRound "+round);
			
			for(String answer: answers){
				for(int i = 0 ;i<getWordCount(answer); i++){
					for(int j = i ;j<getWordCount(answer); j++){
						ArrayList<String> acceptableRules = getAcceptableRules(getSubphrase(answer,i,j));
						for(int k = 0 ; k < acceptableRules.size(); k++){
							String appliedRule = applyRule(answer,i,j,acceptableRules.get(k));
							if(!alreadyConsideredStrings.contains(appliedRule)){
								newAnswers.add(appliedRule);
								alreadyConsideredStrings.add(appliedRule);
								System.out.println(appliedRule);
							}
						}
					}
				}
			}
	
			answers.clear();
			for(String answer: newAnswers)
				answers.add(answer);
			newAnswers.clear();
		}
		
		if(answers.contains(expectedValue))
			success = true;
		
		if(success)
			return "Success";
		else
			return "Failure";
		
	}
		
	public static String applyRule(String sentence,int i,int j,String rule){
		String subphrase = getSubphrase(sentence,i,j);
		String[]parsedRule = rulesParser(rule);
		subphrase = parsedRule[0]; // replaces the subphrase with the left hand side of the rule		
		
		String left = ""; 
		if(i-1>=0)
			left = getSubphrase(sentence,0,i-1);
		
		String right = "";
		if(j!=getWordCount(sentence)-1)
			right = getSubphrase(sentence,j+1,getWordCount(sentence)-1);
			
		String appliedRule = "";
		if(left != "") 
			appliedRule += left + " ";
		
		appliedRule += subphrase;
		
		if(right != "") 
			appliedRule += " " + right;
		
		return appliedRule;
	}
		
		
	public static ArrayList<String> getAcceptableRules(String phrase){
		ArrayList<String> rules = makeRules();
		ArrayList<String> acceptableRules = new ArrayList<String>();
		for(String rule: rules){
			String[]parsedRule = rulesParser(rule);
			if(phrase.equalsIgnoreCase(parsedRule[1]))
					acceptableRules.add(rule);
		}
		return acceptableRules;
	}
	
	
	public static ArrayList<String> makeRules(){
		//Due to bad coding, there is a STRICT format in writing a rule, follow the proper spacing
		ArrayList<String> rules = new ArrayList<String>();
		rules.add("cl -> np vp np");
		rules.add("np -> adj n");
		rules.add("vp -> adv v");
		rules.add("vp -> v");
		rules.add("n -> man");
		rules.add("v -> man");
		rules.add("n -> woman");
		rules.add("adj -> big");
		rules.add("n -> house");
		return rules;
	}
	
	public static String[] rulesParser(String rule){//returns the left and right hand side separately and fixed them
		String[] tokens = rule.split("->");
		tokens[0] = tokens[0].substring(0, tokens[0].length()-1); //removes the space after the left hand side
		tokens[1] = tokens[1].substring(1); //removes the space before the right hand side
		return tokens;
		
	}
	
	public static int getWordCount(String phrase){
		String[] tokens = phrase.split(" ");
		ArrayList<String> toBeCounted = new ArrayList<String>();
		for(String token : tokens)
			if(!token.equals(""))
				toBeCounted.add(token);
		return toBeCounted.size();
	}
	
	public static String getSubphrase(String phrase, int wordIndexFrom, int wordIndexTo){
		String[] tokens = phrase.split(" ");
		ArrayList<String> wordList = new ArrayList<String>();
		for(String token : tokens)
			if(!token.equals(""))
				wordList.add(token);
		String word = "";
		for(int i = wordIndexFrom;i<=wordIndexTo;i++){
			word+=wordList.get(i)+" ";
		}
		word = word.substring(0,word.length()-1);
		return word;
	}

}
